home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / pascala.zip / TREE2.PAS < prev    next >
Pascal/Delphi Source File  |  1991-05-09  |  4KB  |  133 lines
  1. (*********************************************************)
  2. (* Alejo Alamillo            COSC 055                *)
  3. (* Spring 1991            Assignment: TreeMod            *)
  4. (*********************************************************)
  5.  
  6.  
  7. (************************************************************)
  8. (*  Several procedures for binary tree processing are                                       *)
  9. (*  contained in the module below.                                                   *)
  10. (*  This is NOT a complete module ready to link up with a         *)
  11. (*  driver program.        PRB 10/90                                                                               *)
  12. (************************************************************)
  13. PROGRAM TreeMod (Input,Output);
  14.  
  15.   TYPE  DataType = Real;
  16.         NodePointer = ^NodeRec;
  17.         NodeRec= RECORD
  18.                    Data: DataType;
  19.                    Level: 0..Maxint;
  20.                    LeftLink,
  21.                    RightLink: NodePointer;
  22.                  END;
  23.  
  24.   VAR   Head: NodePointer;
  25.         SEED : Integer;
  26.         DataIn: DataType;
  27.  
  28. (***************************************************)
  29. (*  Generates a random number ( 0 <= R < 1 )                         *)
  30. (*  SEED  must be initialized ONCE before using                             *)
  31. (***************************************************)
  32. FUNCTION Random (VAR SEED : Integer): Real;
  33.   CONST Modulus = 65536;
  34.         Multiplier = 25173;
  35.         Increment = 13849;
  36.  
  37.   BEGIN
  38.   SEED :=((Multiplier*SEED ) + Increment) MOD Modulus;
  39.   Random:= SEED /Modulus;
  40.   END;
  41. (***************************************************)
  42. (* Disposes of the nodes of an existing, unneeded  *)
  43. (* Tree.  Recursively called in postorder.        *)
  44. (***************************************************)
  45. PROCEDURE DisposeTree (VAR AquiNode:NodePointer);
  46.  
  47. BEGIN
  48. WITH AquiNode^ DO
  49.   BEGIN
  50.    IF LeftLink<> nil THEN
  51.    DisposeTree (LeftLink);
  52.     IF RightLInk<> nil THEN
  53.      DisposeTree (RightLink);
  54.     Dispose (AquiNode);
  55.   END;
  56. END;
  57. (***************************************************)
  58. (*  Recursively searches for node to insert DataIn *)
  59. (*  Inserts data DataIn into a tree in order       *)
  60. (***************************************************)
  61. PROCEDURE AddNode (VAR Aqui: NodePointer; DataIn: DataType;
  62.                 AquiLevel:  Integer);
  63. BEGIN
  64. IF Aqui = nil THEN     (* Place is found *)
  65.   BEGIN
  66.   New(Aqui);
  67.   Aqui^.Data:= DataIn;
  68.   Aqui^.Level:= AquiLevel;
  69.   Aqui^.LeftLink:= nil;
  70.   Aqui^.RightLink:= nil;
  71.   END
  72. ELSE                    (* Search farther *)
  73.   IF (DataIn < Aqui^.Data) THEN
  74.     AddNode (Aqui^.LeftLink, DataIn, AquiLevel+1)
  75.   ELSE                                            
  76.     AddNode (Aqui^.RightLink, DataIn,AquiLevel+1); (* Duplicate keys   *)
  77. END;                                                     (* are inserted in  *)
  78.                                                          (* original order   *)
  79. (**************************************)
  80. (*                                    *)
  81. (**************************************)
  82.   PROCEDURE FormTree(VAR Head:NodePointer);
  83.     CONST NumberofNodes = 15;
  84.     VAR I: Integer;
  85.         DataIn: DataType;
  86.   (*************************************)
  87.   (*  Currently randomly generated     *)
  88.   (*************************************)
  89.   PROCEDURE GetData(VAR DataIn: DataType);
  90.     BEGIN
  91.     DataIn:=100*Random(SEED )+1;
  92.     END;
  93.  
  94. BEGIN (* FormTree *)
  95. Head:= nil;
  96. FOR I:= 1 TO NumberofNodes DO
  97.   BEGIN
  98.   GetData(DataIn);
  99.   AddNode (Head, DataIn, 0);
  100.   END;
  101. END;
  102. (**********************************************)
  103. (*  SHOWTREE     Recursively displays a tree    *)
  104. (*             in L-R order.                  *)
  105. (**********************************************)
  106. PROCEDURE SHOWTREE  (AquiNode: NodePointer);
  107.  
  108. BEGIN
  109. WITH AquiNode^ DO
  110.   BEGIN                     (* Reversed for rotated display *)
  111.   IF RightLink<> nil THEN
  112.     SHOWTREE  (RightLink);
  113.   WRITELN('   ',Trunc(Data):3*(1+Level));
  114.   IF LeftLink<>nil THEN
  115.     SHOWTREE  (LeftLink);
  116.   END;
  117. END;
  118.  
  119.      (*************  MAIN *************) 
  120.  
  121. BEGIN                                   
  122.  (* Initialize *)
  123.  (* Describe *)
  124.  
  125.  Write('Please enter SEED  for the Random function: ');
  126.   Readln(SEED );  WRITELN;
  127.  
  128.   FormTree(Head);
  129.   WRITELN;  WRITELN;  WRITELN;
  130.   SHOWTREE  (Head);
  131.   DisposeTree (Head);
  132. END.
  133.